1. Field of the Invention
The present invention relates to data packet routing in data communication networks. More particularly, the present invention relates to a method and apparatus of streaming data packet routing to increase data packet throughput.
2. Art Background
Computer networks are implemented for the exchange information from one location to another. The information may be data exchanged between users of the computer network, or data propagated from one user to a peripheral device such as a printer or a remote data storage location. In recent years, networking systems have spread worldwide, increasing the efficiency of users working habits by increasing the volume of information that can be exchanged almost instantaneously from one location to another. The effect has been revolutionary. Today, even person communications and document delivery are handled via electronic mail where, in the past, other means of communicating would have been required.
The proliferation of computer networks has necessitated the development of high speed and complex communications devices. One such device is the data packet router. A packet router is responsible for providing network layer functionality in local and wide area networks. This involves receiving a packet from one network, determining where the packet should be forwarded to, modifying the packet appropriately and sending it to its proper next destination. FIG. 1(a) illustrates a conventional mechanism for a packet routing engine. The packet is received and is stored into a conventional memory array 10. The contents of the data packet stored in memory device 10 are then modified in memory 10 by the modify engine 20. The modified data packet may then be forwarded by reading the data out of memory device 10. This conventional method suffers an undesirable delay due to the load and store times necessary for accessing the memory 10.
Another approach to packet routing is to modify the packet on the fly as it streams towards its destination. Vector processors, such as Cray Computers, can broadly be considered "streaming modify engines", but have not been strictly applied to data packet processing. A conceptual streaming organization is illustrated in FIG. 1(b) which illustrates a streaming packet modification engine 30 which would eliminate the load/store delay that is introduced when packets are modified in a memory. The streaming modification pipeline adds some latency to the process but adds no per packet delay which would otherwise reduce throughput. A problem that would be encountered when applying a streaming modification engine to data packet processing occurs when data in a packet to be modified is dependent on data that follows it in the packet. One example of this is the checksum in the header of an IP packet. As will be described more fully below, the checksum in some protocols may be calculated based on fields both preceding and following the checksum field in the data packet. Thus, using the streaming modify engine architecture of FIG. 1(b) for some data packets would be impossible because the checksum field cannot be forwarded to its destination until the fields following it have been examined to calculate a new checksum field.
It would be desirable, and is therefore an object of the present invention, to achieve the advantages of the packet streaming modification engine implementation for use with packets that include fields that need to be modified on the fly which are dependent on fields that may follow them in the packet.